#pragma once
#include<iostream>
using namespace std;
template<class K,class V>
class BSTreeNode {
public:
	K _key;
	V _value;
	BSTreeNode<K,V>* left;
	BSTreeNode<K,V>* right;

	BSTreeNode(const K& key,const V& value)
		:_key(key),
		_value(value),
		left(nullptr),
		right(nullptr)
	{};

};

template<class K,class V>
class BSTree {
	using Node = BSTreeNode<K,V>;
public:
	BSTree(const BSTree<K, V>& t)
	{
		_root = Copy(t._root);
	}
	~BSTree() {
		destory(_root);
		_root = nullptr;

	}
	bool Insert(const K& key, const V& value) {
		Node* newnode = new Node(key,value);

		if (_root == nullptr) {
			_root = newnode;
			return true;
		}
		
			Node* cur = _root;
			Node* parent =nullptr;
			while (cur) {
				if (key < cur->_key) {
					parent = cur;
					cur = cur->left;
				}
				else if (key > cur->_key) {
					parent = cur;
					cur = cur->right;
				}
				else {
					return false;
				}
			}
			if (parent->_key < key) {
				parent->right = newnode;
			}
			else {
				parent->left = newnode;
			}
			return true;


	}
	 
	Node* Find(const K& key) {
		Node* cur = _root;
		while (cur) {
			if (cur->_key == key) {
				return cur;
			}
			else if(key<cur->_key) {
				cur = cur->left;
			}
			else if (cur->_key > key) {
				cur = cur->right;
			}
		}
		return nullptr;
	}

	bool erase(const K& key) {
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur) {
			if (cur->_key < key) {
				parent = cur;
				cur = cur->right;
			}
			else if (cur->_key > key) {
				parent = cur;
				cur = cur->left;
			}
			else {
				if (cur->left == nullptr) {
					if (parent == nullptr) {
						_root = cur->right;
					}
					if (parent->left == cur) {
						parent->left = cur->right;
					}
					else {
						parent->right = cur->right;
					}
					delete cur;
				}
				else if (cur->right == nullptr) {
					if (parent == nullptr) {
						_root = cur->left;
					}
					if (parent->left == cur) {
						parent->left = cur->left;
					}
					else {
						parent->right = cur->left;
					}
					delete cur;
				}
				else {
					Node* replace = cur->right;
					Node* replaceParent = cur;
					while (replace->left) {
						replaceParent = replace; 
						replace = replace->left;
					}
					cur->_key = replace->_key;
					if (replaceParent->left == replace) {
						replaceParent->left = replace->right;
					}
					else {
						replaceParent->right = replace->right;
					}
					delete replace;
				}
				return true;
			}
		}
	}
		

	void InOrder() {
		_InOrder(_root);
	}
private:
	void destory(Node* root) {
		void Destroy(Node * root)
		{
			if (root == nullptr)
				return;

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

	}
	void _InOrder(Node* root) {
		if (root == nullptr) {
			return;
		}
		_InOrder(root->left);
		cout << root->_key<<" ";
		_InOrder(root->right);
	}
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newRoot = new Node(root->_key, root->_value);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);
		return newRoot;
	}


	Node* _root=nullptr;
};
